package algorithm.t202110;

import java.util.Stack;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/15 8:57
 * @description :5道
 */
public class t20211015 {
    //遍历单链表
    static public void list(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode temp = head;


        while (true) {
            if (temp.next == null) {
                System.out.println(temp);
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }


    }

    //876.链表的中间节点
    public ListNode2 middleNode(ListNode2 head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        ListNode2 temp = head;
        int len = 1;

        while (true) {
            if (temp.next == null) {
                break;
            }
            len++;
            temp = temp.next;

        }

        temp = head;
        int count = len / 2;
        for (int i = 0; i < count; i++) {
            temp = temp.next;
        }

        return temp;

    }


    //19.删除链表的倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return null;
        }

        ListNode temp = head;
        int len = 1;

        while (true) {
            if (temp.next == null) {
                break;
            }
            len++;
            temp = temp.next;

        }
        if (n < 0 || n > len) {
            return null;
        }

        temp = head;
        int count = len - n;
        if (count == 0) {//删除的是头节点
            temp.val = temp.next.val;
            temp.next = temp.next.next;
            return head;

        }
        for (int i = 0; i < count - 1; i++) {
            temp = temp.next;

        }
        temp.next = temp.next.next;
        return head;
    }

    static public ListNode2 removeNthFromEnd2(ListNode2 head, int n) {
        if (head == null) {
            return null;
        }

        //建立一个虚拟头节点
        ListNode2 node0 = new ListNode2(0);
        node0.next = head;

        //快，慢指针
        ListNode2 fast = node0;
        ListNode2 slow = node0;

        //先让快指针移动n次
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        /*for (int i = 1; i <= n+1 ; i++) {
            fast.next = fast.next;
        }*/

        //两个指针共同移动，结束后慢指针指向的便是被删除节点的前驱
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return node0.next;
    }

    //面试题02.05 链表求和
    static public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }


        Stack<Integer> num1 = new Stack<>();
        Stack<Integer> num2 = new Stack<>();
        StringBuilder builder1 = new StringBuilder();
        StringBuilder builder2 = new StringBuilder();


        //遍历第一个链表，获取第一个数
        ListNode n1Pointer = l1;
        while (true) {
            if (n1Pointer.next == null) {
                num1.push(n1Pointer.val);
                break;
            }
            num1.push(n1Pointer.val);
            n1Pointer = n1Pointer.next;
        }
        //得到第一个数
        while (!num1.empty()) {
            builder1.append(num1.pop());
        }

        Integer n1 = Integer.valueOf(builder1.toString());
        System.out.println("得到的第一个数是" + n1);

        //遍历第二个链表，获取第二个数
        ListNode n2Pointer = l2;
        while (true) {
            if (n2Pointer.next == null) {
                num2.push(n2Pointer.val);
                break;
            }
            num2.push(n2Pointer.val);
            n2Pointer = n2Pointer.next;
        }
        //得到第二个数
        while (!num2.empty()) {
            builder2.append(num2.pop());
        }
        Integer n2 = Integer.valueOf(builder2.toString());
        System.out.println("得到的第二个数是" + n2);

        //两者和
        Integer sum = n2 + n1;
        System.out.println("和是" + sum);

        //建立结果链表
        ListNode head = new ListNode();
        //辅助指针
        ListNode pointer = head;
        String res = String.valueOf(sum);

        for (int i = res.length() - 1; i >= 0; i--) {
            int num = res.charAt(i);
            int real = num - 48;
            System.out.println("real" + real);

            ListNode temp = new ListNode(Integer.valueOf(real));
            pointer.next = temp;
            pointer = pointer.next;

        }


        return head.next;
    }

    static public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }

        ListNode dummy = new ListNode();//虚拟节点
        ListNode temp = dummy;//虚拟节点的辅助指针

        int bit = 0;
        while (l1 != null || l2 != null || bit != 0) {
            int sum = bit;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            temp.next = new ListNode(sum % 10);

            bit = sum / 10;

            temp = temp.next;

        }

        return dummy.next;
    }

    //面试题02.06 回文链表
    static public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        if (head.next == null) {
            return true;
        }

        ListNode temp = head;
        //使用栈来完成此题
        Stack<Integer> stack = new Stack<>();

        while (true) {
            if (temp.next == null) {
                stack.push(temp.val);
                break;
            }
            stack.push(temp.val);
            temp = temp.next;

        }

        //将栈中的元素取出，来和链表中的元素比对
        while (true) {
            if (head == null) {
                return true;
            }

            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;

        }

    }

    //面试题02.07 链表相交
    static public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pointerA = headA;
        ListNode pointerB = headB;

        while (pointerA!=pointerB){
            pointerA=pointerA==null?headA:pointerA.next;
            pointerB=pointerB==null?headB:pointerB.next;

        }
        return pointerA;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode();

        ListNode node1 = new ListNode(8);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(5);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        ListNode headx = new ListNode();
        headx.next=new ListNode(15);
        System.out.println(getIntersectionNode(head, headx));

    }

}

class ListNode2 {
    int val;
    ListNode2 next;

    ListNode2() {
    }

    ListNode2(int val) {
        this.val = val;
    }

    ListNode2(int val, ListNode2 next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode2{" +
                "val=" + val +
                '}';
    }
}